#include <taiju/const-balanced-bit-vector.h>

namespace taiju {

const UInt8 ConstBalancedBitVector::table_[8][256] = {
	{
		 0,  2,  0,  4,  0,  4,  0,  6,  0,  2,  0,  6,  0,  6,  0,  8,
		 0,  2,  0,  6,  0,  6,  0,  8,  0,  2,  0,  8,  0,  8,  0, 10,
		 0,  2,  0,  4,  0,  4,  0,  8,  0,  2,  0,  8,  0,  8,  0, 10,
		 0,  2,  0,  8,  0,  8,  0, 10,  0,  2,  0, 10,  0, 10,  0, 12,
		 0,  2,  0,  4,  0,  4,  0,  8,  0,  2,  0,  8,  0,  8,  0, 10,
		 0,  2,  0,  8,  0,  8,  0, 10,  0,  2,  0, 10,  0, 10,  0, 12,
		 0,  2,  0,  4,  0,  4,  0, 10,  0,  2,  0, 10,  0, 10,  0, 12,
		 0,  2,  0, 10,  0, 10,  0, 12,  0,  2,  0, 12,  0, 12,  0, 14,
		 0,  2,  0,  4,  0,  4,  0,  6,  0,  2,  0,  6,  0,  6,  0, 10,
		 0,  2,  0,  6,  0,  6,  0, 10,  0,  2,  0, 10,  0, 10,  0, 12,
		 0,  2,  0,  4,  0,  4,  0, 10,  0,  2,  0, 10,  0, 10,  0, 12,
		 0,  2,  0, 10,  0, 10,  0, 12,  0,  2,  0, 12,  0, 12,  0, 14,
		 0,  2,  0,  4,  0,  4,  0, 10,  0,  2,  0, 10,  0, 10,  0, 12,
		 0,  2,  0, 10,  0, 10,  0, 12,  0,  2,  0, 12,  0, 12,  0, 14,
		 0,  2,  0,  4,  0,  4,  0, 12,  0,  2,  0, 12,  0, 12,  0, 14,
		 0,  2,  0, 12,  0, 12,  0, 14,  0,  2,  0, 14,  0, 14,  0, 16
	},
	{
		 1,  3,  3,  5,  1,  5,  5,  7,  1,  5,  5,  7,  1,  7,  7,  9,
		 1,  3,  3,  7,  1,  7,  7,  9,  1,  7,  7,  9,  1,  9,  9, 11,
		 1,  3,  3,  7,  1,  7,  7,  9,  1,  7,  7,  9,  1,  9,  9, 11,
		 1,  3,  3,  9,  1,  9,  9, 11,  1,  9,  9, 11,  1, 11, 11, 13,
		 1,  3,  3,  5,  1,  5,  5,  9,  1,  5,  5,  9,  1,  9,  9, 11,
		 1,  3,  3,  9,  1,  9,  9, 11,  1,  9,  9, 11,  1, 11, 11, 13,
		 1,  3,  3,  9,  1,  9,  9, 11,  1,  9,  9, 11,  1, 11, 11, 13,
		 1,  3,  3, 11,  1, 11, 11, 13,  1, 11, 11, 13,  1, 13, 13, 15,
		 1,  3,  3,  5,  1,  5,  5,  9,  1,  5,  5,  9,  1,  9,  9, 11,
		 1,  3,  3,  9,  1,  9,  9, 11,  1,  9,  9, 11,  1, 11, 11, 13,
		 1,  3,  3,  9,  1,  9,  9, 11,  1,  9,  9, 11,  1, 11, 11, 13,
		 1,  3,  3, 11,  1, 11, 11, 13,  1, 11, 11, 13,  1, 13, 13, 15,
		 1,  3,  3,  5,  1,  5,  5, 11,  1,  5,  5, 11,  1, 11, 11, 13,
		 1,  3,  3, 11,  1, 11, 11, 13,  1, 11, 11, 13,  1, 13, 13, 15,
		 1,  3,  3, 11,  1, 11, 11, 13,  1, 11, 11, 13,  1, 13, 13, 15,
		 1,  3,  3, 13,  1, 13, 13, 15,  1, 13, 13, 15,  1, 15, 15, 17
	},
	{
		 2,  4,  4,  6,  4,  6,  6,  8,  2,  6,  6,  8,  6,  8,  8, 10,
		 2,  6,  6,  8,  6,  8,  8, 10,  2,  8,  8, 10,  8, 10, 10, 12,
		 2,  4,  4,  8,  4,  8,  8, 10,  2,  8,  8, 10,  8, 10, 10, 12,
		 2,  8,  8, 10,  8, 10, 10, 12,  2, 10, 10, 12, 10, 12, 12, 14,
		 2,  4,  4,  8,  4,  8,  8, 10,  2,  8,  8, 10,  8, 10, 10, 12,
		 2,  8,  8, 10,  8, 10, 10, 12,  2, 10, 10, 12, 10, 12, 12, 14,
		 2,  4,  4, 10,  4, 10, 10, 12,  2, 10, 10, 12, 10, 12, 12, 14,
		 2, 10, 10, 12, 10, 12, 12, 14,  2, 12, 12, 14, 12, 14, 14, 16,
		 2,  4,  4,  6,  4,  6,  6, 10,  2,  6,  6, 10,  6, 10, 10, 12,
		 2,  6,  6, 10,  6, 10, 10, 12,  2, 10, 10, 12, 10, 12, 12, 14,
		 2,  4,  4, 10,  4, 10, 10, 12,  2, 10, 10, 12, 10, 12, 12, 14,
		 2, 10, 10, 12, 10, 12, 12, 14,  2, 12, 12, 14, 12, 14, 14, 16,
		 2,  4,  4, 10,  4, 10, 10, 12,  2, 10, 10, 12, 10, 12, 12, 14,
		 2, 10, 10, 12, 10, 12, 12, 14,  2, 12, 12, 14, 12, 14, 14, 16,
		 2,  4,  4, 12,  4, 12, 12, 14,  2, 12, 12, 14, 12, 14, 14, 16,
		 2, 12, 12, 14, 12, 14, 14, 16,  2, 14, 14, 16, 14, 16, 16, 18
	},
	{
		 3,  5,  5,  7,  5,  7,  7,  9,  5,  7,  7,  9,  7,  9,  9, 11,
		 3,  7,  7,  9,  7,  9,  9, 11,  7,  9,  9, 11,  9, 11, 11, 13,
		 3,  7,  7,  9,  7,  9,  9, 11,  7,  9,  9, 11,  9, 11, 11, 13,
		 3,  9,  9, 11,  9, 11, 11, 13,  9, 11, 11, 13, 11, 13, 13, 15,
		 3,  5,  5,  9,  5,  9,  9, 11,  5,  9,  9, 11,  9, 11, 11, 13,
		 3,  9,  9, 11,  9, 11, 11, 13,  9, 11, 11, 13, 11, 13, 13, 15,
		 3,  9,  9, 11,  9, 11, 11, 13,  9, 11, 11, 13, 11, 13, 13, 15,
		 3, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		 3,  5,  5,  9,  5,  9,  9, 11,  5,  9,  9, 11,  9, 11, 11, 13,
		 3,  9,  9, 11,  9, 11, 11, 13,  9, 11, 11, 13, 11, 13, 13, 15,
		 3,  9,  9, 11,  9, 11, 11, 13,  9, 11, 11, 13, 11, 13, 13, 15,
		 3, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		 3,  5,  5, 11,  5, 11, 11, 13,  5, 11, 11, 13, 11, 13, 13, 15,
		 3, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		 3, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		 3, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19
	},
	{
		 4,  6,  6,  8,  6,  8,  8, 10,  6,  8,  8, 10,  8, 10, 10, 12,
		 6,  8,  8, 10,  8, 10, 10, 12,  8, 10, 10, 12, 10, 12, 12, 14,
		 4,  8,  8, 10,  8, 10, 10, 12,  8, 10, 10, 12, 10, 12, 12, 14,
		 8, 10, 10, 12, 10, 12, 12, 14, 10, 12, 12, 14, 12, 14, 14, 16,
		 4,  8,  8, 10,  8, 10, 10, 12,  8, 10, 10, 12, 10, 12, 12, 14,
		 8, 10, 10, 12, 10, 12, 12, 14, 10, 12, 12, 14, 12, 14, 14, 16,
		 4, 10, 10, 12, 10, 12, 12, 14, 10, 12, 12, 14, 12, 14, 14, 16,
		10, 12, 12, 14, 12, 14, 14, 16, 12, 14, 14, 16, 14, 16, 16, 18,
		 4,  6,  6, 10,  6, 10, 10, 12,  6, 10, 10, 12, 10, 12, 12, 14,
		 6, 10, 10, 12, 10, 12, 12, 14, 10, 12, 12, 14, 12, 14, 14, 16,
		 4, 10, 10, 12, 10, 12, 12, 14, 10, 12, 12, 14, 12, 14, 14, 16,
		10, 12, 12, 14, 12, 14, 14, 16, 12, 14, 14, 16, 14, 16, 16, 18,
		 4, 10, 10, 12, 10, 12, 12, 14, 10, 12, 12, 14, 12, 14, 14, 16,
		10, 12, 12, 14, 12, 14, 14, 16, 12, 14, 14, 16, 14, 16, 16, 18,
		 4, 12, 12, 14, 12, 14, 14, 16, 12, 14, 14, 16, 14, 16, 16, 18,
		12, 14, 14, 16, 14, 16, 16, 18, 14, 16, 16, 18, 16, 18, 18, 20
	},
	{
		 5,  7,  7,  9,  7,  9,  9, 11,  7,  9,  9, 11,  9, 11, 11, 13,
		 7,  9,  9, 11,  9, 11, 11, 13,  9, 11, 11, 13, 11, 13, 13, 15,
		 7,  9,  9, 11,  9, 11, 11, 13,  9, 11, 11, 13, 11, 13, 13, 15,
		 9, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		 5,  9,  9, 11,  9, 11, 11, 13,  9, 11, 11, 13, 11, 13, 13, 15,
		 9, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		 9, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		11, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19,
		 5,  9,  9, 11,  9, 11, 11, 13,  9, 11, 11, 13, 11, 13, 13, 15,
		 9, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		 9, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		11, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19,
		 5, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		11, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19,
		11, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19,
		13, 15, 15, 17, 15, 17, 17, 19, 15, 17, 17, 19, 17, 19, 19, 21
	},
	{
		 6,  8,  8, 10,  8, 10, 10, 12,  8, 10, 10, 12, 10, 12, 12, 14,
		 8, 10, 10, 12, 10, 12, 12, 14, 10, 12, 12, 14, 12, 14, 14, 16,
		 8, 10, 10, 12, 10, 12, 12, 14, 10, 12, 12, 14, 12, 14, 14, 16,
		10, 12, 12, 14, 12, 14, 14, 16, 12, 14, 14, 16, 14, 16, 16, 18,
		 8, 10, 10, 12, 10, 12, 12, 14, 10, 12, 12, 14, 12, 14, 14, 16,
		10, 12, 12, 14, 12, 14, 14, 16, 12, 14, 14, 16, 14, 16, 16, 18,
		10, 12, 12, 14, 12, 14, 14, 16, 12, 14, 14, 16, 14, 16, 16, 18,
		12, 14, 14, 16, 14, 16, 16, 18, 14, 16, 16, 18, 16, 18, 18, 20,
		 6, 10, 10, 12, 10, 12, 12, 14, 10, 12, 12, 14, 12, 14, 14, 16,
		10, 12, 12, 14, 12, 14, 14, 16, 12, 14, 14, 16, 14, 16, 16, 18,
		10, 12, 12, 14, 12, 14, 14, 16, 12, 14, 14, 16, 14, 16, 16, 18,
		12, 14, 14, 16, 14, 16, 16, 18, 14, 16, 16, 18, 16, 18, 18, 20,
		10, 12, 12, 14, 12, 14, 14, 16, 12, 14, 14, 16, 14, 16, 16, 18,
		12, 14, 14, 16, 14, 16, 16, 18, 14, 16, 16, 18, 16, 18, 18, 20,
		12, 14, 14, 16, 14, 16, 16, 18, 14, 16, 16, 18, 16, 18, 18, 20,
		14, 16, 16, 18, 16, 18, 18, 20, 16, 18, 18, 20, 18, 20, 20, 22
	},
	{
		 7,  9,  9, 11,  9, 11, 11, 13,  9, 11, 11, 13, 11, 13, 13, 15,
		 9, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		 9, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		11, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19,
		 9, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		11, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19,
		11, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19,
		13, 15, 15, 17, 15, 17, 17, 19, 15, 17, 17, 19, 17, 19, 19, 21,
		 9, 11, 11, 13, 11, 13, 13, 15, 11, 13, 13, 15, 13, 15, 15, 17,
		11, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19,
		11, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19,
		13, 15, 15, 17, 15, 17, 17, 19, 15, 17, 17, 19, 17, 19, 19, 21,
		11, 13, 13, 15, 13, 15, 15, 17, 13, 15, 15, 17, 15, 17, 17, 19,
		13, 15, 15, 17, 15, 17, 17, 19, 15, 17, 17, 19, 17, 19, 19, 21,
		13, 15, 15, 17, 15, 17, 17, 19, 15, 17, 17, 19, 17, 19, 19, 21,
		15, 17, 17, 19, 17, 19, 19, 21, 17, 19, 19, 21, 19, 21, 21, 23
	}
};

UInt64 ConstBalancedBitVector::findclose(UInt64 id) const
{
	UInt64 is_far_id = objs_.rank(id) - 1;
	if (is_fars_[is_far_id])
	{
		UInt64 is_pioneer_id = is_fars_.rank(is_far_id) - 1;
		UInt64 pioneer_id = is_pioneers_.rank(is_pioneer_id) - 1;
		UInt64 pioneer = static_cast<UInt64>(pioneers_[pioneer_id])
			* NUM_BITS_PER_UNIT;

		UInt64 unit = objs_.units()[pioneer / NUM_BITS_PER_UNIT];
		UInt64 excess = objs_.excess(pioneer - 1) - (objs_.excess(id) - 1);

		return pioneer + lookup(unit, excess);
	}

	++id;
	UInt64 unit_id = id / NUM_BITS_PER_UNIT;
	UInt64 bit_id = id % NUM_BITS_PER_UNIT;
	UInt64 unit = objs_.units()[unit_id] >> bit_id;
	if (bit_id != 0)
		unit |= objs_.units()[unit_id + 1] << (NUM_BITS_PER_UNIT - bit_id);
	return id + lookup(unit, 1);
}

UInt64 ConstBalancedBitVector::size() const
{
	return objs_.size() + is_fars_.size() + is_pioneers_.size()
		+ pioneers_.size();
}

void ConstBalancedBitVector::clear()
{
	objs_.clear();
	is_fars_.clear();
	is_pioneers_.clear();
	pioneers_.clear();
}

void ConstBalancedBitVector::swap(ConstBalancedBitVector *target)
{
	objs_.swap(&target->objs_);
	is_fars_.swap(&target->is_fars_);
	is_pioneers_.swap(&target->is_pioneers_);
	pioneers_.swap(&target->pioneers_);
}

const void *ConstBalancedBitVector::map(Mapper mapper)
{
	ConstBalancedBitVector temp;

	mapper = temp.objs_.map(mapper);
	mapper = temp.is_fars_.map(mapper);
	mapper = temp.is_pioneers_.map(mapper);
	mapper = temp.pioneers_.map(mapper);

	swap(&temp);

	return mapper.address();
}

void ConstBalancedBitVector::read(Reader reader)
{
	ConstBalancedBitVector temp;

	temp.objs_.read(reader);
	temp.is_fars_.read(reader);
	temp.is_pioneers_.read(reader);
	temp.pioneers_.read(reader);

	swap(&temp);
}

void ConstBalancedBitVector::write(Writer writer) const
{
	objs_.write(writer);
	is_fars_.write(writer);
	is_pioneers_.write(writer);
	pioneers_.write(writer);
}

inline UInt64 ConstBalancedBitVector::lookup(UInt64 unit, UInt64 excess)
{
	UInt64 id = 0;
	for ( ; ; )
	{
		if (excess <= 8)
		{
			UInt8 value = table_[excess - 1][unit & 0xFF];
			if (value < 8)
				return id + value;
			excess = value - 7;
		}
		else
		{
			UInt8 value = table_[7][unit & 0xFF];
			excess += value - 15;
		}
		unit >>= 8;
		id += 8;
	}
}

}  // namespace taiju
